◀ Prev · Parts · Full · Next ▶

The Ville construction suggests that the Mises–Wald–Church sense of randomness is not good enough, because some random sequences do not satisfy some laws of randomness. For example, the Ville construction does not satisfy one of the laws of the iterated logarithm: lim sup n → → ∞ ∞ − − ∑ ∑ k = 1 n ( x k − − 1 / 2 ) 2 n log ⁡ ⁡ log ⁡ ⁡ n ≠ ≠ 1 {\displaystyle \limsup _{n\to \infty }{\frac {-\sum _{k=1}^{n}(x_{k}-1/2)}{\sqrt {2n\log \log n}}}\neq 1} Naively, one can fix this by requiring a sequence to satisfy all possible laws of randomness, where a "law of randomness" is a property that is satisfied by all sequences with probability 1. However, for each infinite sequence y 1 : ∞ ∞ ∈ ∈ 2 N {\displaystyle y_{1:\infty }\in 2^{\mathbb {N} }} , we have a law of randomness that x 1 : ∞ ∞ ≠ ≠ y 1 : ∞ ∞ {\displaystyle x_{1:\infty }\neq y_{1:\infty }} , leading to the conclusion that there are no random sequences.

(Per Martin-Löf, 1966)cite-ref-6[6] defined "Martin-Löf randomness" by only allowing laws of randomness that are Turing-computable. In other words, a sequence is random iff it passes all Turing-computable tests of randomness.

The thesis that the definition of Martin-Löf randomness "correctly" captures the intuitive notion of randomness has been called the Martin-Löf–Chaitin Thesis; it is somewhat similar to the Church–Turing thesis.cite-ref-7[7]

◀ Prev · Parts · Full · Next ▶